A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once, except, in some types of memory, upon a block erase. WOM-codes were originally designed for memories that consist of binary memory elements that could physically only be changed from a zero state to a one state. Examples of such memories are punch cards and optical disks. More recently, WOM-codes have been designed for general usage in different types of memories, including flash memories. See, e.g., A. Jiang, “On the Generalization of Error-Correcting WOM-codes,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 1391-1395, Nice, France (2007); A. Jiang and J. Bruck, “Joint coding for flash memory storage,” in Proc. IEEE Int. Symp. Inform. Theory, pp. 1741-1745, Toronto, Canada, (July 2008); H. Mandavifar, P. H. Siegel, A. Vardy, J. K. Wolf, and E. Yaakobi, “A Nearly Optimal Construction of Flash Codes,” in Proc. IEEE Int. Symp. Inform. Theory. pp. 1239-1243, Seoul, Korea, (July 2009).
A WOM-code allows the reuse of a write-once medium by introducing redundancy into the recorded bit sequence and, in subsequent write operations, observing the state of the medium before determining how to update the contents of the memory with a new bit sequence.
A simple example enables the recording of two bits of information in 3 memory elements, twice. The encoding and decoding rules for this WOM-code are described in a tabular form in the table below. It is easy to verify that after the first 2-bit data vector is encoded into a 3-bit codeword, if the second 2-bit data vector is different from the first, the 3-bit codeword into which it is encoded does not change any code bit 1 into a code bit 0, ensuring that it can be recorded in the write-once medium.
Data BitsFirst WriteSecond Write00000111101000110101010111001110
The sum-rate of the WOM-code is the sum of all the individual rates for each write. While there are different ways to analyze the efficiency of WOM-codes, we find that the appropriate figure of merit is to analyze the sum-rate under the assumption of a fixed number of writes. In general, the more writes the WOM-code can support, the better the sum-rate it can achieve. The goal is to give upper and lower bounds on the sum-rates of WOM-codes while fixing the number of writes t to a desired number.